/*
题目链接：https://leetcode.cn/problems/numbers-with-repeated-digits/description/
题目标题：1012.至少有1位重复的数字
提交时间：2024/10/7
*/

class Solution {
public:
    map<int,int>m;
    int numDupDigitsAtMostN(int n) {
        string str = to_string(n);
        if(n<10) return 0;   
        int c=0;  //用来记录n的位数,2位起步
        int N=n;
        while(N){
            c++;
            N/=10;
        }
        int ans=0;  //初始值为9
        int num=9;   
        for(int i=0;i<c-1;i++){   //1~n的位数所有数之和
            ans+=num;     //计算到位c数的前一位,组合数学
            num*=(9-i);     
        }
        //当到达第c位时
        ans+=dp(0,false,str);   //ans表示每一位都不重复的数目
        int answer=n-ans;
        return answer;
    }
    int dp(int mask,bool smallnum,string &str)   //make记录前面使用过的数字（从高位比起）
    {                                 //smallnum表示当前前缀是否小n的前缀
    if(__builtin_popcount(mask)==str.size()) return 1;
    int k=mask*2+(smallnum?1:0);
    if(!m.count(k)){
        int ans=0;
        int l=mask==0?1:0;   //1表示已用，0表示未用
        int u=smallnum?9:str[__builtin_popcount(mask)]-'0';
        for(int i=l;i<=u;i++){
            if(((mask>>i)&1)==0){    //查看对应位数是否已用
                ans+=dp(mask|(1<<i),smallnum||i<u,str);
            }
        }
        m[k]=ans;
    }
    return m[k];
    }
};